package com.datastructure.test.nextpermutation;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class NextPermutation {

    public static void main(String[] args) {
        NextPermutation nextPermutation = new NextPermutation();
        int[] nums = {3,2,1};
        int[] ints = nextPermutation.nextPermutation(nums);
        System.out.println(ints);
    }

    public int[] nextPermutation (int[] nums) {
        // write code here
        if(nums==null){
            return nums;
        }
        int length = nums.length;
        if(length ==1){
            return nums;
        }
        int[] temp = new int[length];
        System.arraycopy(nums,0,temp,0, length);
        Arrays.sort(temp);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        LinkedList<Integer> linkedList =new LinkedList<>();
        ArrayList<Integer> list;
        boolean isFind;
        boolean[] isUsed = new boolean[length];
        dfs(temp,res,linkedList,isUsed,length);
        int i = 0;
        for (; i < res.size(); i++) {
            list=res.get(i);
            isFind=true;
            for (int j = 0; j < list.size(); j++) {
                Integer integer = list.get(j);
                if(integer !=nums[j]){
                    isFind=false;
                    break;
                }
            }
            if(isFind){
                break;
            }
        }
        int size = res.size();
        if(i==(size-1)||i== size){
            list= res.get(0);
            for (int j = 0; j < list.size(); j++) {
                temp[j]= list.get(j);
            }
        } else {
            list= res.get(i+1);
            for (int j = 0; j < list.size(); j++) {
                temp[j]= list.get(j);
            }
        }
        return temp;
    }

    private void dfs(int[] nums, ArrayList<ArrayList<Integer>> res, LinkedList<Integer> linkedList, boolean[] isUsed, int length) {
        if(linkedList.size()==length){
            res.add(new ArrayList<>(linkedList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(isUsed[i]){
                continue;
            }
            if(i>0&&nums[i]==nums[i-1]&&!isUsed[i]){
                continue;
            }
            isUsed[i]=true;
            linkedList.add(nums[i]);
            dfs(nums,res,linkedList,isUsed,length);
            isUsed[i]=false;
            linkedList.removeLast();
        }
    }

    public int[] nextPermutation1 (int[] nums) {
        // write code here
        for (int i = nums.length-1; i >= 0; i--) {
            for (int j = nums.length-1; j > i; j--) {
                if (nums[j] > nums[i]) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    Arrays.sort(nums,i+1,nums.length);
                    return nums;
                }
            }
        }
        Arrays.sort(nums);
        return nums;
    }
}
